home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / delaunay.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  5.6 KB  |  223 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  delaunay_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*****************************************************************************
  18. +
  19. +    Delaunay tree    by Olivier Devillers
  20. +
  21. +        Fully dynamic construction of the Delaunay triangulation with
  22. +        good randomized complexity
  23. +
  24. +    Copyright (c) 1990
  25. +    INRIA, 2004 route des Lucioles, 06 565 Valbonne Cedex, France
  26. +
  27. +
  28. +    for LEDA
  29. +    Copyright (c) 1990  by  Fachbereich 14,  Informatik
  30. +    Universitaet des Saarlandes, 6600 Saarbruecken, FRG
  31. +     All rights reserved.
  32. +
  33. ******************************************************************************/
  34.  
  35. #include <LEDA/plane.h>
  36.  
  37. typedef double coord;
  38.  
  39. struct NOEUD;
  40. typedef NOEUD* noeud;
  41.  
  42. struct STAR;
  43. typedef STAR* star;
  44.  
  45. struct REINSERER;
  46. typedef REINSERER* reinserer;
  47.  
  48. struct LISTENOEUD;
  49. typedef LISTENOEUD* listenoeud;
  50.  
  51.  
  52. struct DT_POINT{
  53.     coord x,y;
  54.         void* i;
  55.     int  n;                   /* un flag dont l'ordre est compatible avec
  56.                           l'ordre d'insertion */
  57.     int  visite;           /* un flag de visite */
  58.     NOEUD* cree;    /*un noeud cree par l'insertion de ce point*/
  59. }; 
  60.  
  61. typedef DT_POINT* DT_item;
  62.  
  63. declare(list,DT_item)
  64.  
  65.  
  66. typedef void delaunay_f2(double,double);
  67. typedef void delaunay_f4(double,double,double,double);
  68. typedef void delaunay_f6(double,double,double,double,double,double);
  69. typedef void delaunay_F6(double,double,double,double,double*,double*);
  70.  
  71.  
  72.  
  73. class delaunay_tree{
  74.  
  75.         int flag;        /* numero de l'operation en cours */
  76.         noeud nouveau;        /* dernier noeud cree */
  77.         
  78.         star Star;        /* pour la suppression */
  79.         reinserer Reinsert;
  80.  
  81.     NOEUD * arbre ;        /* la racinne du Delaunay tree */
  82.     NOEUD * last ;        /* dernier noeud cree */
  83.  
  84.         int counter;            /* total number of items (s.n.) */
  85.  
  86.  
  87.  
  88. char*      used_blocks;
  89. DT_item    Poubelle_point;
  90. listenoeud Poubelle_listenoeud;
  91. noeud      Poubelle_noeud;
  92. noeud      Libre_noeud;
  93. star       Poubelle_star;
  94. reinserer  Poubelle_reinserer;
  95.  
  96. int fl;
  97.  
  98. int item_nombre;
  99. DT_item item_next;
  100.  
  101. int listenoeud_nombre;
  102. listenoeud listenoeud_next;
  103.  
  104. int noeud_nombre;
  105. noeud noeud_next;
  106.  
  107. int star_nombre;
  108. star star_next;
  109.  
  110. int reinserer_nombre;
  111. reinserer reinserer_next;
  112.  
  113. star first_star;
  114.  
  115.  
  116.  
  117. char*      alloc_block(int size);
  118. void       free_blocks();
  119. void       poubelle_point(DT_item p);
  120. DT_item    vrai_alloc_point();
  121. DT_item    alloc_point();
  122. void       poubelle_listenoeud(listenoeud p);
  123. listenoeud vrai_alloc_listenoeud();
  124. listenoeud alloc_listenoeud();
  125. void       poubelle_noeud(noeud p);
  126. noeud      vrai_alloc_noeud();
  127. noeud      alloc_noeud();
  128. void       poubelle_star(star p);
  129. star       vrai_alloc_star();
  130. star       alloc_star();
  131. void       poubelle_reinserer( reinserer p);
  132. reinserer  vrai_alloc_reinserer();
  133. reinserer  alloc_reinserer();
  134.  
  135. void  beaufils( noeud bf, noeud bp);
  136. void  plusbeaufils( noeud bf, noeud bp);
  137. void  demiplan( noeud t);
  138. void  cercle( noeud t);
  139. int   confondu( DT_item a, DT_item b);
  140. int   direct( noeud n);
  141. int   conflit( noeud n, DT_item p);
  142. noeud Insert( noeud n, DT_item p);
  143. noeud creenoeud( noeud pere, int i, DT_item p);
  144. int   creation( noeud detruit, DT_item p);
  145. DT_item localise( noeud detecte, DT_item p);
  146. void  add_x1x2( reinserer r, noeud v, DT_item p);
  147. void  add_decroche( reinserer r, noeud v);
  148. void  destroy( noeud u, DT_item p);
  149. void  recherche( DT_item p);
  150. void  reinsertion( reinserer n, DT_item p);
  151. void  parcours( reinserer n, DT_item p);
  152. void  trace_items(noeud, delaunay_f2*);
  153. void  list_items(noeud n, list(DT_item)& L);
  154. void  clear_items(noeud n);
  155. void  del_noeud( noeud n, delaunay_f4* trace_segment,int both);
  156. void  vor( noeud n, delaunay_f6* trace_segment, delaunay_F6* pt_infi, int both);
  157.  
  158. virtual void copy_inf(ent& p)  { p=p; }
  159. virtual void clear_inf(ent& p) { p=0; }
  160.  
  161. public:
  162.  
  163.  delaunay_tree();
  164. ~delaunay_tree();
  165.  
  166. reinserer locate( reinserer n, DT_item x);
  167. void clear_Reinsert( reinserer n);
  168. void clear_Star();
  169. void init_Star( noeud n, int i, int j, int k);
  170. star loc_Star( DT_item xx);
  171. void split_Star( star n1,star n2);
  172.  
  173. DT_item insert(double, double, void*);
  174. DT_item insert(point p, void* inf) { return insert(p.xcoord(),p.ycoord(),inf); }
  175. DT_item neighbor(double, double);
  176. DT_item neighbor(point p)          { return neighbor(p.xcoord(),p.ycoord()); }
  177. void    del(double, double);
  178. void    del(point p)               { del(p.xcoord(),p.ycoord()); }
  179. void    del_item( DT_item);
  180.  
  181. point    key(DT_item p)  { return point(p->x,p->y); } 
  182. void*    inf(DT_item p)  { return p->i; } 
  183.  
  184. void     change_inf(DT_item p, void* i)  { copy_inf(i);  
  185.                                            clear_inf(p->i); 
  186.                                            p->i = i; } 
  187.  
  188. void     trace_voronoi_sites( delaunay_f2*);
  189. void     trace_voronoi_edges( delaunay_f6*, delaunay_F6*, int both = 0);
  190. void     trace_triang_edges( delaunay_f4* , int both = 0);
  191.  
  192. void     all_items(list(DT_item)&);
  193.  
  194. void     convex_hull(list(DT_item)&);
  195.  
  196. void     clear();
  197. void     init();
  198.  
  199. };
  200.  
  201.  
  202.  
  203. #define DELAUNAY_TREE(itype) name2(itype,_DELAUNAY_TREE)
  204.  
  205. #define DELAUNAY_TREEdeclare(itype)\
  206. \
  207. struct DELAUNAY_TREE(itype) : public delaunay_tree{\
  208. \
  209. void copy_inf(ent& p)  { Copy(*(itype*)&p); }\
  210. void clear_inf(ent& p) { Clear(*(itype*)&p); }\
  211. \
  212. DT_item insert(point site, itype i)\
  213.                           { return delaunay_tree::insert(site,Ent(i)); }\
  214. \
  215. itype  inf(DT_item p)    { return itype(delaunay_tree::inf(p)); } \
  216. \
  217.  DELAUNAY_TREE(itype)() {};\
  218. ~DELAUNAY_TREE(itype)() {};\
  219. \
  220. };
  221.  
  222.  
  223.